/*
	
*/
#ifndef _watershed_H_
  #define _watershed_H_



#include "..\support.h"

template <typename T>
int watershed(const pip::Image<T> &in, pip::Image<T> &output,const pip::Image<T> mark){
	//init Images
	pip::Image<float> out(in.dimension());
	pip::Image<T>    dist(in.dimension());
	out.fill(-1);
	dist.fill(0);
	//init magic numbers
	const float  WSHED(0),MASK(-2);
	float curr_dist(0),label(0);
	//init STD	
	std::queue<Pixel> fifo;
	std::vector<std::vector<Pixel> > levels;
	FIsort(in,levels);
	std::vector<Pixel> neigh;
	std::vector<Pixel>::iterator i,j;
	Pixel p,p_;
	//marker-pixel to mark end of 'run'
	Pixel marker(-1,-1,-1); // marker.negative()==true
	for(unsigned int h=0; h < levels.size();++h){  //flooding
		for(i= levels[h].begin(); i <  levels[h].end(); ++i){
			if(i->get(in)==T(h)){
				i->set(out,MASK);	
			    i->getNeighbors(in,neigh);
				for(j = neigh.begin(); j < neigh.end(); ++j){
					if(   j->get(out) >= 0){
						i->set(dist,T(1));
						fifo.push(*i);
					}
				}
			}
		}
		curr_dist=1;
		fifo.push(marker);
		while(true){  //basins growing
			p=fifo.front();
			fifo.pop();
			if(p.negative()){  // marker.negative()==true
				if(fifo.empty()){
				   break;
				}else{
					fifo.push(marker);
					++curr_dist;
					p=fifo.front();
					fifo.pop();
				}
			}
			p.getNeighbors(in,neigh);
			for(j = neigh.begin(); j < neigh.end(); ++j){
				if(   j->get(dist) < curr_dist
					&& j->get(out) >= 0){        //basin or watershed
						if(j->get(out) > 0){
							if(   p.get(out)==MASK
								|| p.get(out)==WSHED){
									p.set(out,j->get(out));
							}else if(j->get(out)!= p.get(out)){
								p.set(out,WSHED);
							}
						}else if(p.get(out)==MASK){
							p.set(out,WSHED);
						}
				}else if(   j->get(out)==MASK     //plateau pixel
						 && j->get(dist)==0){
							 j->set(dist,T(curr_dist+1));
							 fifo.push(*j);
				}
			 }
		}
		for(int z=0; z < in.dim(2); ++z){
			for(int y=0; y < in.dim(1); ++y){
				for(int x=0; x < in.dim(0); ++x){
					if(in(x,y,z)==T(h)){
						dist(x,y,z)=0;
						if(    out(x,y,z)==MASK
							&& mark(x,y,z)==unsigned char(255)
							){
							++label;
							fifo.push(Pixel(x,y,z));
							out(x,y,z)=T(label);
							while(!fifo.empty()){
								p=fifo.front();
								fifo.pop();
								p.getNeighbors(in,neigh);
								for(j = neigh.begin(); j < neigh.end(); ++j){
									if(j->get(out)==MASK){
										fifo.push(*j);
										j->set(out,label);
									}
								}
							}
						}
					}
				}
			}
		}
	}

	output = convertAllToUnsignedChar(out);
	pip::exportFile(out,"float_result.pip");
	return 0;//what??!
}

#endif